package d_ch12.floyed;

import java.util.Arrays;

import c_ch11.WeightedGraph;

public class Floyed_try {

    private WeightedGraph G;
    private int[][] dis; //[源][目标点]
    private boolean hasNegCycle = false;

    public Floyed_try(WeightedGraph G){

        this.G = G;

        dis = new int[G.V()][G.V()];
        for(int v = 0; v < G.V(); v ++)
            Arrays.fill(dis[v], Integer.MAX_VALUE);  //一般稀疏图居多，全填为不可达；

        for(int v = 0; v < G.V(); v ++){		//然后导入图所有E的权值；
            dis[v][v] = 0;
            for(int w: G.adj(v))
                dis[v][w] = G.getWeight(v, w);
        }

        	for(int v = 0; v < G.V(); v ++)  //源；
                for(int w = 0; w < G.V(); w ++) //目标；
                	for(int tf = 0; tf < G.V(); tf ++)	 //transfer;这一行可以在最上边，也可以在这儿；只要不影响v-w的配对就好；  
                    if(dis[v][tf] != Integer.MAX_VALUE && dis[tf][w] != Integer.MAX_VALUE //各边的权值都已经初始化在dis里了
                       && dis[v][tf] + dis[tf][w] < dis[v][w])				//前俩判断防止溢出
                        dis[v][w] = dis[v][tf] + dis[tf][w];

        for(int v = 0; v < G.V(); v ++)  //[源][目标点]可以为同一个点，亦把所有顶点中转了一遍，也就是说临边肯定周转过；把所有这类顶点遍历一遍，本来应该是0的，如果临边连有负权环，中转后肯定择小变成了负数；
            if(dis[v][v] < 0)											//有负权环的话也会导致其从0变为负数，毕竟"那个模型"可以表示任何点边情况，可以去看看图片；
                hasNegCycle = true;
    }

    public boolean hasNegativeCycle(){
        return hasNegCycle;
    }

    public boolean isConnectedTo(int v, int w){
        G.validateVertex(v);
        G.validateVertex(w);
        return dis[v][w] != Integer.MAX_VALUE;
    }

    public int distTo(int v, int w){
        G.validateVertex(v);
        G.validateVertex(w);
        return dis[v][w];
    }

    static public void main(String[] args){

        WeightedGraph g = new WeightedGraph("g2_ch12.txt");
        Floyed_try floyed = new Floyed_try(g);
        
            for(int v = 0; v < g.V(); v ++){
                    System.out.print(floyed.distTo(v, v) + " ");
                System.out.println();
            }

        WeightedGraph g2 = new WeightedGraph("g_ch12.txt");
        Floyed_try floyed2 = new Floyed_try(g2);
        if(!floyed2.hasNegativeCycle()){
            for(int v = 0; v < g.V(); v ++){
                for(int w = 0; w < g.V(); w ++)
                    System.out.print(floyed2.distTo(v, w) + " ");
                System.out.println();
            }
        }
        else
            System.out.println("exist negative cycle.");
    }
}
